/*
练习5-1 顺序存储的二叉树的遍历
分数 25
作者 陈越
单位 浙江大学

对顺序存储方式存放的二叉树，给出前序、中序和后序遍历的非递归算法实现。
函数接口定义：

void PreOrder(BinaryTree tree);
void InOrder(BinaryTree tree);
void PostOrder(BinaryTree tree);

其中 BinaryTree 相关的数据类型的定义如下：

typedef char TElemSet; // 树结点元素为单个字符 
#define NIL '-'        // 表示空指针的字符 
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet *data; // 数据元素顺序表 
    int size;       // 顺序表长度 
};

三个遍历函数中，对结点的访问定义为输出该结点中存储的字符，前后无空格。

输入样例：

13
ABC-DE------F

输出样例：

ABDCEF
BDAEFC
DBFECA
*/

#include <stdio.h>
#include <stdlib.h>

typedef char TElemSet; /* 树结点元素为单个字符 */
#define NIL '-' /* 表示空指针的字符 */
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet *data; /* 数据元素顺序表 */
    int size;       /* 顺序表长度 */
};

void PreOrder(BinaryTree tree);
void InOrder(BinaryTree tree);
void PostOrder(BinaryTree tree);

int main(void)
{
    BinaryTree tree;
    int n, i; 
    
    scanf("%d\n", &n);
    tree = (BinaryTree)malloc(sizeof(struct BinaryTreeNode));
    tree->data = (char *)malloc(sizeof(char) * (n+1));
    tree->size = n;
    tree->data[0] = NIL;
    for (i=1; i<=n; i++) {
        scanf("%c", &tree->data[i]);
    }
    PreOrder(tree);
    printf("\n");
    InOrder(tree);
    printf("\n");
    PostOrder(tree);
    printf("\n");
     
    return 0;
}
/* 你的代码将被嵌在这里 */

// 定义辅助的栈结构
typedef struct StackNode *Stack;
struct StackNode {
    int *data;
    int top;
};

// 初始化栈
Stack InitStack(int size) {
    Stack stack = (Stack)malloc(sizeof(struct StackNode));
    stack->data = (int *)malloc(sizeof(int) * size);
    stack->top = 0;
    return stack;
}

// 压栈
void Push(Stack stack, int x) {
    stack->data[stack->top++] = x;
}

// 弹栈
int Pop(Stack stack) {
    return stack->data[--stack->top];
}

// 获取栈顶元素
int Top(Stack stack) {
    return stack->data[stack->top - 1];
}

// 判断栈是否为空
int IsEmpty(Stack stack) {
    return stack->top == 0;
}

// 释放栈
void FreeStack(Stack stack) {
    free(stack->data);
    free(stack);
}

// 前序遍历
void PreOrder(BinaryTree tree) {
    int nodeIdx = 1;
    Stack stack = InitStack(tree->size+2);
    while ((nodeIdx <= tree->size && tree->data[nodeIdx] != NIL) || !IsEmpty(stack)) {
        while (nodeIdx <= tree->size && tree->data[nodeIdx] != NIL) {
            printf("%c", tree->data[nodeIdx]);
            // 一直向左并将沿途结点压入栈
            Push(stack, nodeIdx);
            nodeIdx = nodeIdx * 2;
        }
        if (!IsEmpty(stack)) {
            // 转向右子树
            nodeIdx = Pop(stack) * 2 + 1;
        }
    }
    FreeStack(stack);
}

// 遇到一个结点，就把它压栈，并去遍历它的左子树；
// 当左子树遍历结束后，从栈顶弹出这个结点并访问它；
// 然后按其右指针再去中序遍历该结点的右子树。
void InOrder(BinaryTree tree) {
    int nodeIdx = 1;
    Stack stack = InitStack(tree->size+2);
    while ((nodeIdx <= tree->size && tree->data[nodeIdx] != NIL) || !IsEmpty(stack)) {
        while (nodeIdx <= tree->size && tree->data[nodeIdx] != NIL) {
            // 一直向左并将沿途结点压入栈
            Push(stack, nodeIdx);
            nodeIdx = nodeIdx * 2;
        }
        if (!IsEmpty(stack)) {
            nodeIdx = Pop(stack);
            printf("%c", tree->data[nodeIdx]);
            // 转向右子树
            nodeIdx = nodeIdx * 2 + 1;
        }
    }
    FreeStack(stack);
}

void PostOrder(BinaryTree tree) {
    int nodeIdx = 1;
    Stack stack = InitStack(tree->size+2);
    int lastVisit = 0;
    while ((nodeIdx <= tree->size && tree->data[nodeIdx] != NIL) || !IsEmpty(stack)) {
        while (nodeIdx <= tree->size && tree->data[nodeIdx] != NIL) {
            // 一直向左并将沿途结点压入栈
            Push(stack, nodeIdx);
            nodeIdx = nodeIdx * 2;
        }
        if (!IsEmpty(stack)) {
            nodeIdx = Top(stack);
            int rightIdx = nodeIdx * 2 + 1;
            if (rightIdx <= tree->size && tree->data[rightIdx] != NIL && lastVisit != rightIdx) {
                // 若右子树存在，且未被访问过，转向右子树
                nodeIdx = rightIdx;
            } else {
                // 访问结点
                nodeIdx = Pop(stack);
                printf("%c", tree->data[nodeIdx]);
                lastVisit = nodeIdx;
                nodeIdx = tree->size + 1; // 结束循环
            }
        }
    }
    FreeStack(stack);
}
